//
// Created by LiuYou on 2021/8/2.
//
/*

 build-in array & raw pointer
 STL array
 STL vector

 */


#include <cstdlib>
#include <cstdio>
#include <algorithm>


//bool duplication(int array[], int length, int* duplication) {
//    if (array == nullptr || length <= 0) {
//        return false;
//    }
//    for (int i = 0; i < length; ++i) {
//        if (array[i] < 0 || array[i] > length - 1) {
//            return false;
//        }
//    }
//    for (int i = 0; i < length; ++i) {
//        while (array[i] != i) {
//            if (array[i] == array[array[i]]) {
//                *duplication = array[i];
//                return true;
//            }
//            // 交换 array[i]和array[array[i]]
//            int temp = array[i];
//            array[i] = array[temp];
//            array[temp] = temp;
//        }
//    }
//    return false;
//}


bool duplication(int* array, int length, int* duplication) {
    // 判断输入是否合法
    if (array == nullptr || length <= 0) {
        return false;
    }
    // 判断输入是否合法
    for (int i = 0; i < length; ++i) {
        if (array[i] < 0 || array[i] > length - 1) {
            return false;
        }
    }
    // 算法
    for (int i = 0; i < length; ++i) {
        while (array[i] != i) {
            if (array[i] == array[array[i]]) {
                *duplication = array[i];
                return true;
            }
            // 交换 array[i]和array[array[i]]
//            int temp = array[i];
//            array[i] = array[temp];
//            array[temp] = temp;
            std::swap( array[i], array[array[i]] );
        }
    }
    return false;
}


/*
 * 3. 数组中重复的数字
 */
int main() {
    int integerArray[7] = {2, 3, 1, 0, 2, 5, 3};
    int dup = 0;
    // 获取数组长度。
    size_t arraySize = sizeof( integerArray ) / sizeof( int );
    duplication( integerArray, arraySize, &dup );
    fprintf( stdout, "dup: %d\n", dup );
    fprintf( stdout, "array size: %d\n", arraySize );


    exit( 0 );
}